package com.dyz.leetcode;

public class Exist79 {
    int n;
    int m;
    int w;
    char[] letters;
    char[][] board;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        this.n = board.length;
        this.m = board[0].length;
        this.w = word.length();
        this.letters = word.toCharArray();
        this.board = board;
        this.visited = new boolean[n][m];

        //字符的起始点
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                boolean res = search(i,j,0);
                if(res){return true;}
            }
        }
        return false;
    }
    private boolean search(int i, int j, int k){
        //终止条件1
        if(w==k){return true;}
        //终止条件2
        if(i<0 || j<0 || i>=n || j>=m|| board[i][j]!=letters[k] || visited[i][j]){return false;}

        //访问过
        visited[i][j] =true;

        //四个方向搜索
        boolean res = search(i+1, j, k+1) || search(i,j+1,k+1)||search(i-1, j, k+1) || search(i, j-1, k+1);

        //回退
        visited[i][j] = false;

        return res;
    }
}
